package cn.edu.jxau.test;

import java.util.Arrays;

public class IndexMinPQ {

    public static void main(String[] args) {

        int[] arr1 = { 1, 3, 4, 6, 7, 8, 9 };
        int[] arr2 = { 1, 4, 6, 7, 8, 9 };
        int[] arr3 = { 1, 5, 6, 7, 8 };
        int[] arr4 = { 2, 3, 4, 5, 6, 7 };
        int[] arr = merge(arr1, arr2, arr3, arr4);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 多向归并
     * 
     * @param arrs 要多向归并的数组,其中各个数组有序
     * @return
     */
    private static int[] merge(int[]... arrs) {

        int len = 0;
        int[] arrIndex = new int[arrs.length];
        for (int[] arr : arrs) {
            System.out.println(Arrays.toString(arr));
            len += arr.length;
        }
        IndexMinPQ indexMinPQ = new IndexMinPQ(arrs.length);
        for (int i = 0; i < arrs.length; i++) {
            indexMinPQ.insert(i, arrs[i][0]);
            arrIndex[i]++;
        }
        System.out.println(indexMinPQ);
        int[] arr = new int[len];
        int i = 0;
        while (!indexMinPQ.isEmpty()) {
            arr[i++] = indexMinPQ.minKey();
            int index = indexMinPQ.delMin();
            if(arrIndex[index] < arrs[index].length) {
                indexMinPQ.insert(index, arrs[index][arrIndex[index]++]);
            }
        }
        return arr;
    }

    /**
     * 优先队列大小
     */
    private int size;

    /**
     * 堆到{@code keyArr}的映射，用于获取二叉堆中某号元素在数据集中的位置，
     * 比如pq[1]=9，说明堆的1号位元素在keyArr的9号位，keyArr[pq[1]]
     * 则是取出堆的1号位元素
     */
    private int[] pq;

    /**
     * {@code keyArr}到堆的映射，用于获取数据集中某号元素在堆中的位置，
     * 比如qp[1]=2，说明keyArr的1号位元素在堆的2号位。由此可得转换关系
     * pq[qp[i]] == qp[pq[i]] == i
     */
    private int[] qp;

    /**
     * 数据集
     */
    private int[] keyArr;

    private int max;

    public IndexMinPQ(int capacity) {

        max = capacity;
        pq = new int[capacity + 1];
        qp = new int[capacity + 1];
        keyArr = new int[capacity];
        for (int i = 0; i < qp.length; i++) {
            pq[i] = -1;
            qp[i] = -1;
        }
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public boolean contains(int i) {
        return qp[i] != -1;
    }

    /**
     * 获取堆顶元素在{@code keyArr}中的索引
     * @return
     */
    public int minIndex() {

        if (isEmpty()) {
            throw new RuntimeException("优先队列已为空");
        }
        return pq[1];
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public int minKey() {

        if (isEmpty()) {
            throw new RuntimeException("优先队列已为空");
        }
        return keyArr[pq[1]];
    }

    public void insert(int i, int key) {

        if (i < 0 || i >= max) {
            throw new RuntimeException("优先队列已满");
        }
        if (contains(i)) { // 修改
            changeKey(i, key);
        }

        keyArr[i] = key;
        size++;
        pq[size] = i;
        qp[i] = size;
        swim(size);
    }

    public void changeKey(int i, int key) {

        if (!contains(i)) {
            throw new RuntimeException("优先队列i处不包含元素");
        }

        if (key > keyArr[i]) { // 变大了，下沉
            keyArr[i] = key;
            sink(qp[i]);
        } else if (key < keyArr[i]) { // 变小了，上浮
            keyArr[i] = key;
            swim(qp[i]);
        } else {
            // 没有改变，nothing to do
        }
    }

    /**
     * 删除最小值，并返回其索引
     * @return
     */
    public int delMin() {

        if (isEmpty()) {
            throw new RuntimeException("优先队列为空");
        }
        int minIndex = minIndex();
        delete(minIndex);
        return minIndex;
    }

    public void delete(int i) {

        if (!contains(i)) {
            throw new RuntimeException("优先队列i出不包含元素");
        }
        int pqi = qp[i];
        swap(pqi, size--);
        sink(pqi);
        swim(pqi);
        qp[i] = -1; // 删除keyArr到堆的映射
        pq[size + 1] = -1; // 删除堆到keyArr的映射
    }

    /**
     * 上浮调整堆
     * 
     * @param k
     */
    private void swim(int k) {

        while (k > 1 && keyArr[pq[k]] < keyArr[pq[k / 2]]) {
            swap(k, k / 2);
            k /= 2;
        }
    }

    /**
     * 下浮调整堆
     * 
     * @param k
     */
    private void sink(int k) {

        while (2 * k <= size) {
            int i = 2 * k;
            if (i < size && keyArr[pq[i]] > keyArr[pq[i + 1]]) { // 找出更小的一个
                i++;
            }
            if (keyArr[pq[k]] <= keyArr[pq[i]]) {
                break;
            }
            swap(k, i);
            k = i;
        }
    }

    /**
     * 交换优先队列中i,j元素的位置,映射也
     * 需要一起修改
     * 
     * @param i
     * @param j
     */
    private void swap(int i, int j) {

        int temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;

        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

    @Override
    public String toString() {

        StringBuilder builder = new StringBuilder();
        builder.append("size:").append(size).append("\t");
        builder.append("[");
        for (int i = 1; i <= size; i++) {
            builder.append(keyArr[pq[i]]).append(",");
        }
        if (size != 0) {
            builder.deleteCharAt(builder.length() - 1);
        }
        builder.append("]");
        return builder.toString();
    }
}
